package 双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 四数之和8 {
    //https://leetcode.cn/problems/4sum/
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        //List<List<Integer>> ret = new ArrayList<List<Integer>>();
        List<List<Integer>> ret = new ArrayList<>();
        int n = nums.length;
        int cur1 = 0;
        while(cur1 < n - 3) {
            int cur2 = cur1 + 1;
            while(cur2 < n - 2) {
                int letf = cur2 + 1, right = n - 1;
                long sum = (long) target - nums[cur1] - nums[cur2];//加法减法计算会有溢出，这里减得过小了
                while(letf < right) {
                    if(nums[letf] + nums[right] > sum) {
                        right--;
                        while(letf < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }else if(nums[letf] + nums[right] < sum) {
                        letf++;
                        while(letf < right && nums[letf] == nums[letf - 1]) {
                            letf++;
                        }
                    }else {
                        ret.add(new ArrayList<>(Arrays.asList(nums[cur1],nums[cur2],nums[letf],nums[right])));
                        letf++;
                        right--;
                        while(letf < right && nums[letf] == nums[letf - 1]) {
                            letf++;
                        }
                        while(letf < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
                cur2++;
                while(cur2 < n - 2 && nums[cur2] == nums[cur2 - 1]) {
                    cur2++;
                }
            }
            cur1++;
            while(cur1 < n - 3 && nums[cur1] == nums[cur1 - 1]) {
                cur1++;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        long sum = (long) -294967296 - 1000000000 - 1000000000;//计算时默认以int范围内进行计算，这里会溢出，强转成 在long范围内进行计算 就不会溢出
        System.out.println(sum);
    }
}
